#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

#define SWAP(a, b) {	\
	int t = a;			\
	a = b;				\
	b = t;				\
}

/**********************************************************************
 *                          COMMENT                                   *
 **********************************************************************/
// greatest common dividor
// gcd(b, 0) = b;          (b != 0)
// d = gcd(a, b) = gcd(b, r)   (a >= b, a = b * q + r,  0 <= r < b)
// gcd(a, b) = gcd(b, r) = ... = gcd(d, 0) = d
int gcd(int a, int b) {
	if (a < b) {
		SWAP(a, b);
	}
	while (b != 0) {
		int r = a % b;
		a = b;
		b = r;
	} // b == 0
	return a;
}

int main(void) {

	return 0;
}